#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
const int maxm=2, mods=1000000007, size=1<<(5*maxm), sizen=100;
const int tab[10]={
0b01010,
0b01000,
0b10010,
0b11100,
0b01001,
0b10101,
0b00110,
0b11000,
0b10111,
0b11101};

int tabb[size], m;
void initTab() {
    memset(tabb, -1, sizeof tabb);
    if (m==1) {
        for (int i=0; i<10; i++) tabb[tab[i]]=i;
    } else {
        for (int i=0; i<10; i++) {
            for (int j=0; j<10; j++) {
                tabb[(tab[i]<<5)+tab[j]] = i*10+j;
            }
        }
    }
}

int gen(int x) {return m==1 ? tab[x] : (tab[x/10]<<5)+tab[x%10];}

void mulVec(ll *c, ll *a, ll *b) {
    int n=(1<<(m*5));
    for (int i=0; i<n; i++) {
        c[i]=0;
        for (int j=0; j<n; j++) {
            c[i] = (c[i]+a[j]*b[i^j]%mods)%mods;
        }
    }
}

void powVec(ll *a, ll n) {
    ll s[2][size], t[2][size];
    memset(s, 0, sizeof s);
    memset(t, 0, sizeof t);
    s[0][0] = 1;
    memcpy(t[0], a, sizeof t[0]);
    int i=0, j=0;
    for (; n; n/=2) {
        if (n&1) {
            mulVec(s[!i], s[i], t[j]);
            i=!i;
        }
        mulVec(t[!j], t[j], t[j]);
        j=!j;
    }
    memcpy(a, s[i], sizeof s[i]);
}

void initVec(ll n, ll *a) {
    for (int i=0; i<m*5; i++) a[1<<i]=1;
    powVec(a, n);
}

void mulMat(ll c[][sizen], ll a[][sizen], ll b[][sizen]) {
    int n=m==1 ? 10 : 100;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            c[i][j] = 0;
            for (int k=0; k<n; k++) {
                c[i][j] = (c[i][j]+a[i][k]*b[k][j]%mods)%mods;
            }
        }
    }
}

void powMat(ll a[][sizen], ll n) {
    ll s[2][sizen][sizen], t[2][sizen][sizen];
    memset(s, 0, sizeof s);
    memset(t, 0, sizeof t);
    int temp = m==1 ? 10 : 100;
    for (int i=0; i<temp; i++) s[0][i][i]=1;
    memcpy(t[0], a, sizeof t[0]);
    int i=0, j=0;
    for (; n; n/=2) {
        if (n&1) {
            mulMat(s[!i], s[i], t[j]);
            i=!i;
        }
        mulMat(t[!j], t[j], t[j]);
        j=!j;
    }
    memcpy(a, s[i], sizeof s[i]);
}

void initMat(ll n, ll a[][sizen], ll *v) {
    int t = m==1 ? 10 : 100;
    for (int i=0; i<t; i++) {
        for (int j=0; j<t; j++) {
            a[i][j] = v[gen(i)^gen(j)];
        }
    }
    powMat(a, n);
}

int main() {
    freopen("display.in", "r", stdin);
    freopen("display.out", "w", stdout);

    ll n, k;
    int x;
    scanf("%d %lld %lld %d", &m, &n, &k, &x);
    initTab();

    static ll trk[size], trn[3][sizen][sizen];
    initVec(k, trk);
    initMat(n/k, trn[1], trk);
    memset(trk, 0, sizeof trk);
    initVec(n%k, trk);
    initMat(1, trn[2], trk);
    mulMat(trn[0], trn[1], trn[2]);

    int t = m==1 ? 10 : 100;
    for (int i=0; i<t; i++) printf("%lld\n", trn[0][x][i]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}
